package com.celan.year2022.day1226;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            //每次取末尾数字
            int tmp = x % 10;
            //判断是否 大于 最大32位整数
            if (res > 214748364 || (res == 214748364 && tmp > 7)) {
                return 0;
            }
            //判断是否 小于 最小32位整数
            if (res < -214748364 || (res == -214748364 && tmp < -8)) {
                return 0;
            }
            res = res * 10 + tmp;
            x /= 10;
        }
        return res;
    }

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        used = new boolean[nums.length];

        backTrack(0);
        return res;
    }

    void backTrack(int idx) {
        if (path.size() == nums.length) {
            ArrayList<Integer> list = new ArrayList<>(path);
            res.add(list);
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backTrack(i + 1);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}
